package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)783. 二叉搜索树结点最小距离
 * (done)94. 二叉树的中序遍历
 * (done)897. 递增顺序查找树
 * (done)144. 二叉树的前序遍历
 * (done)145. 二叉树的后序遍历
 * (done)98. 验证二叉搜索树
 * 
 * @author: jie.deng
 * @time: 2019年1月19日 下午4:29:09
 */
public class MySolution0120 {
	
	/**
	 * 783. 二叉搜索树结点最小距离
	 * 
   * 给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
   * 
   * 示例：
   * 
   * 输入: root = [4,2,6,1,3,null,null]
   * 输出: 1
   * 解释:
   * 注意，root是树结点对象(TreeNode object)，而不是数组。
   * 
   * 给定的树 [4,2,6,1,3,null,null] 可表示为下图:
   * 
   *           4
   *         /   \
   *       2      6
   *      / \    
   *     1   3  
   * 
   * 最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
   * 注意：
   * 
   * 二叉树的大小范围在 2 到 100。
   * 二叉树总是有效的，每个节点的值都是整数，且不重复。
	 * @param root
	 * @return
	 */
    public int minDiffInBST(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root != null) {
			inorderTraversal(root.left, list);
			list.add(root.val);
			inorderTraversal(root.right, list);
		}

		int minDiff = Integer.MAX_VALUE;
		int len = list.size();
		for (int i = 1; i < len; i++) {
			int diff = list.get(i).intValue() - list.get(i - 1).intValue();
			if (diff < minDiff) {
				minDiff = diff;
			}
		}
		return minDiff;
    }
    
    /**
     * 94. 二叉树的中序遍历
     * 
     * 给定一个二叉树，返回它的中序 遍历。
     * 
     * 示例:
     * 
     * 输入: [1,null,2,3]
     *    1
     *     \
     *      2
     *     /
     *    3
     * 
     * 输出: [1,3,2]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root != null) {
			inorderTraversal(root.left, list);
			list.add(root.val);
			inorderTraversal(root.right, list);
		}
		return list;
	}

	private void inorderTraversal(TreeNode node, List<Integer> list) {
		if (node != null) {
			inorderTraversal(node.left, list);
			list.add(node.val);
			inorderTraversal(node.right, list);
		}
	}

	/**
     * 897. 递增顺序查找树
     * 
     * 给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
     * 
     *  
     * 
     * 示例 ：
     * 
     * 输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
     * 
     *        5
     *       / \
     *     3    6
     *    / \    \
     *   2   4    8
     *  /        / \ 
     * 1        7   9
     * 
     * 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
     * 
     *  1
     *   \
     *    2
     *     \
     *      3
     *       \
     *        4
     *         \
     *          5
     *           \
     *            6
     *             \
     *              7
     *               \
     *                8
     *                 \
     *                  9  
     *  
     * 
     * 提示：
     * 
     * 给定树中的结点数介于 1 和 100 之间。
     * 每个结点都有一个从 0 到 1000 范围内的唯一整数值。
     * @param root
     * @return
     */
	public TreeNode increasingBST(TreeNode root) {
		List<Integer> list = inorderTraversal(root);
		Integer rootVal = list.get(0);
		TreeNode retRoot = new TreeNode(rootVal);
		TreeNode cur = retRoot;
		for (int i = 1; i < list.size(); i++) {
			cur.right = new TreeNode(list.get(i));
			cur = cur.right;
		}
		return retRoot;
	}

	/**
     * 144. 二叉树的前序遍历
     * 
     * 给定一个二叉树，返回它的 前序 遍历。
     * 
     *  示例:
     * 
     * 输入: [1,null,2,3]  
     *    1
     *     \
     *      2
     *     /
     *    3 
     * 
     * 输出: [1,2,3]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root != null) {
			list.add(root.val);
			preorderTraversal(root.left, list);
			preorderTraversal(root.right, list);
		}
		return list;
	}

	private void preorderTraversal(TreeNode node, List<Integer> list) {
		if (node != null) {
			list.add(node.val);
			preorderTraversal(node.left, list);
			preorderTraversal(node.right, list);
		}
	}

	/**
     * 145. 二叉树的后序遍历
     * 
     * 给定一个二叉树，返回它的 后序 遍历。
     * 
     * 示例:
     * 
     * 输入: [1,null,2,3]  
     *    1
     *     \
     *      2
     *     /
     *    3 
     * 
     * 输出: [3,2,1]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root != null) {
			postorderTraversal(root.left, list);
			postorderTraversal(root.right, list);
			list.add(root.val);
		}
		return list;
	}

	private void postorderTraversal(TreeNode node, List<Integer> list) {
		if (node != null) {
			postorderTraversal(node.left, list);
			postorderTraversal(node.right, list);
			list.add(node.val);
		}
	}

	/**
     * 98. 验证二叉搜索树
     * 
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     * 
     * 假设一个二叉搜索树具有如下特征：
     * 
     * 节点的左子树只包含小于当前节点的数。
     * 节点的右子树只包含大于当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * 示例 1:
     * 
     * 输入:
     *     2
     *    / \
     *   1   3
     * 输出: true
     * 示例 2:
     * 
     * 输入:
     *     5
     *    / \
     *   1   4
     *      / \
     *     3   6
     * 输出: false
     * 解释: 输入为: [5,1,4,null,null,3,6]。
     *      根节点的值为 5 ，但是其右子节点值为 4 。
     * @param root
     * @return
     */
	public boolean isValidBST(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isValidBST(root.left, null, root.val) && isValidBST(root.right, root.val, null);
	}

	private boolean isValidBST(TreeNode node, Integer min, Integer max) {
		if (node == null) {
			return true;
		}
		return (min == null || node.val > min) && (max == null || node.val < max)
				&& isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
	}

}
